11584 - Partitioning by palindromes/11584.cpp

   1 /*
   2   Problem:
   3   Andrés Mejía-Posada (andmej@gmail.com)
   4  */
   5 using namespace std;
   6 #include <algorithm>
   7 #include <iostream>
   8 #include <iterator>
   9 #include <sstream>
  10 #include <fstream>
  11 #include <numeric>
  12 #include <cassert>
  13 #include <climits>
  14 #include <cstdlib>
  15 #include <cstring>
  16 #include <string>
  17 #include <cstdio>
  18 #include <vector>
  19 #include <cmath>
  20 #include <queue>
  21 #include <deque>
  22 #include <stack>
  23 #include <list>
  24 #include <map>
  25 #include <set>
  26
  27 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  28 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  29 #define D(x) cout << #x " is " << x << endl
  30
  31 int dp[1005];
  32 bool good[1005][1005];
  33
  34
  35 int main(){
  36   int cases;
  37   cin >> cases;
  38   string s;
  39   while (cases--){
  40     cin >> s;
  41     s = " " + s;
  42     int n = s.size();
  43
  44     for (int i=0; i<n; ++i){
  45       good[i][i] = true;
  46       if (i + 1 < n){
  47         good[i][i+1] = s[i] == s[i+1];
  48       }
  49     }
  50     for (int d=2; d<=n; ++d){
  51       for (int i=0, j; (j = i + d)<n; ++i){
  52         good[i][j] = good[i+1][j-1] && (s[i] == s[j]);
  53       }
  54     }
  55
  56     dp[0] = 0;
  57     for (int i=1; i<n; ++i){
  58       dp[i] = n + 5;
  59       string t = "";
  60       for (int j=i; j>0; --j){
  61         t += s[j];
  62         if (good[j][i]){
  63           dp[i] = min(dp[i], dp[j-1] + 1);
  64         }
  65       }
  66     }
  67     cout << dp[n-1] << endl;
  68   }
  69   return 0;
  70 }